package com.mj;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;
import com.mj.printer.BinaryTreeInfo;

@SuppressWarnings({ "unused", "rawtypes" })
public class BinarySearchTree<E> extends BinaryTree<E>  {
	private Comparator<E> comparator;
	private int i;
		
	public BinarySearchTree() {
		this(null);
	}

	public BinarySearchTree(Comparator<E> comparator) {
		this.comparator = comparator;
	}

	@SuppressWarnings("null")
	public void add(E element) {
		elementNotNullCheck(element);
		if (root == null) {
			root = new Node<>(element, null);
			size++;
			return;
		}
		Node<E> node = root;
		Node<E> parent = null;
		int cmp = 0;
		while (node != null) {
			 cmp = compare(element,node.element);
			 parent = node;
			if (cmp > 0) {
				node = node.right;
			}else if (cmp < 0) {
				node = node.left;
			}else {
				return;
			}
		}
		Node<E> newNode = new Node<>(element, parent);
		if (cmp > 0) {
			parent.right = newNode;
		}else {
			parent.left = newNode;
		}
		size++;
	}
	
	
	public void remove(E element) {
		remove(node(element));
	}
	
	private void remove(Node<E> node) {
		if (node == null) {
			return;
		}
		size--;
		
		if (node.hasTwoChildren()) {
			Node<E> p = successor(node);
			node.element = p.element;
			node = p;
		}
		
		Node<E> replacement = node.left != null ? node.left : node.right;
		if (replacement != null) {
			if (node.parent == null) {
				root = replacement;
				replacement.parent = null;
			}else if (replacement.parent == node.parent.left) {
				node.parent.left = replacement;
			}else if (replacement.parent == node.parent.right) {
				node.parent.right = replacement;
			}
		}else {
			if (node.parent == null) {
				root = null;
			}
			else if (node.parent.left == node) {
				node.parent.left = null;
			}else if (node.parent.right == node) {
				node.parent.right = null;
			}
		}
	}
	
	
//	public void deleteNode(E element) {
//		deleteNode(root, node(element));
//	}
//	
//	public Node<E> deleteNode(Node<E> root,Node<E> element) {
//		if (root == null) {
//			return null;
//		}
//		
//		return null;
//	}
	
	private Node<E> node(E element) {
		Node<E> node = root;
		while (node != null) {
			int cmp = compare(element, node.element);
			if (cmp == 0) {
				return node;
			}else if (cmp > 0) {
				node = node.right;
			}else {
				node = node.left;
			}
		}
		return null;
	}
	

	
    private void elementNotNullCheck(E element) {
        if (element == null) {
            throw new IllegalArgumentException("element must not be null");
        }
    }
    
    @SuppressWarnings("unchecked")
	private int compare(E e1, E e2) {
    	if (comparator == null) {
    		return ((Comparable<E>)e1).compareTo(e2);
		}
		return comparator.compare(e1, e2);
	}
    
    public  static abstract class  Visitor<E> {
        public	boolean stop;
    	public abstract	boolean visit(E element);
    }
}
